//
// Delaunay Triangulation
//
// Homework of CG lesson (Fall 2009) in Tsinghua University.
// All rights reserved.
//

#pragma once

#include "edge.h"
#include "point2d.h"
#include "dcel.h"

#include <vector>

using namespace std;

/**
 * Stores le and re which are the ccw CH edge out of the leftmost vertex
 * and the cw CH edge out of the rightmost vertex, respectively.
 */
 struct MaxEdge
 {
     MaxEdge(void)
     {
         le = NULL;
         re = NULL;
     }

     Edge* le;
	 Edge* re;
 };

 /**
  * Class for delaunay triangulation.
  */
class DelaunayTriangulation
{
// public constructors & destructor
public:
    DelaunayTriangulation(void);

// public member functions
public:
    /**
     * Initials the point data.
     */
    void initial(int* count, Point2d* ps);
	 void initial_nw(int* count, Point2d* ps);
    /**
     * Destroys and resets the edge data.
     */
    void destroy(void);
    /**
     * Does delaunay triangulation operation.
     */
    void doDelaunayTriangulation(void);
	/**
	 * Gets the @c pos point.
	 */
	Point2d* point(int pos) const;

// private member functions
private:
    /**
     * Collects dcel for deleting.
     */
    void collectDcel(Edge* e, vector<DCEL*> &dcels);
	/**
	 * DAC algorithm for delaunay triangulation.
	 */
	MaxEdge delaunay(int begin, int end);

// public data members
public:
    int nPoints;
    Point2d *points;
    MaxEdge maxEdge;
    bool isFinished;
};
